/*
 * Ken Anderson, 2009
 */

#ifndef GRAPH_H
#define GRAPH_H

#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include "util.h"

// Declaration
class Edge;

// Nodes are essentially traversible locations on a graph.  
// We specify x and y coordinates in this implementation for visualization purposes.
class Node
{
protected:
	int mID;
	std::vector<Edge> mOutEdges;		// Could use a separate data structure for edges (map), but this is faster.
	
	// optional
	float mXLoc;			// for visualization
	float mYLoc;			// for visualization
	
public:
	Node(int ID, float xLoc, float yLoc);
	~Node();
	int GetID() { return mID; };
	unsigned int NumOutEdges() { return mOutEdges.size(); };
	Edge* GetOutEdge( unsigned int index ) { return &mOutEdges[index]; } ;
	void AddEdge(Edge edge) ;
	float GetX() { return mXLoc; };
	float GetY() { return mYLoc; };
	void SetX( float x ) { mXLoc = x; };
	void SetY( float y ) { mYLoc = y; };
};

// Edges connect two nodes together.
// Edges are uni-directional, and weighted.
class Edge
{
protected:
	int mID;
	Node* mFromNode;
	Node* mToNode;
	float mWeight;
	
public:
	Edge( int id, Node * from, Node * to, float weight );
	~Edge() {};

	// Getters and setters
	void SetWeight(float weight) { mWeight=weight; };
	float GetWeight() { return mWeight; };
	Node* ToNode() { return mToNode; };
	Node* FromNode() { return mFromNode; };
	int GetID() { return mID; };
};

// Graphs consist of nodes and edges.
// May be overloaded for graphs with specific characteristics.
class Graph
{
protected:
	int mNodeIdCount;
	int mEdgeIdCount;
	std::vector<Node> mNodes;

public:
	Graph();
	virtual ~Graph();
	
	// Warning -- Very inefficient method.  Do not use often! Only used in map creation.
	Node* GetNode( float x, float y ); 
	// Warning - using the return value to get a node pointer isn't safe until the graph is finalized!!
	int AddNode(float xLoc, float yLoc);
	int AddEdge(Node * from, Node * to, float weight);

	unsigned int GetNumOfNodes() { return mNodes.size(); };
	Node* GetNode( unsigned int index ) { return &mNodes[index]; };
	Edge* GetEdge( Node* from, Node* to ) ;
	Node* GetRandomNode() { return GetNode( rand()%GetNumOfNodes() ); };

	virtual void print(FILE * stream);
};

// A map is essentially a 2D grid (four-connected gridworld).
// Nodes may be located at integer coordinates, and may be connected to up to four neighboring nodes.
// The weight of each edge is 1.
// The graph is essentially undirected because for each edge, e(from,to), there is a corresponding edge, e'(to,from).
class Map : public Graph
{
protected:
	unsigned int mWidth;
	unsigned int mHeight;
	
	void Init(unsigned int width, unsigned int height, const char* wallMap);

public:
	// Example uasage:
	/*Map map(20,10, 
		".....#....#...#.#.##" 
		".##..###..###.#...#." 
		".#..#.##....#...#..." 
		".##.#..#.......##..#"
		"..........#.#.######"
		".#####.##...#......#"
		"........############"
		"#.#...###.#..#......"
		"..#.......#.#..#.#.#"
		".######........#.#.."
		); */
	Map(unsigned int width, unsigned int height, const char* wallMap);
	// Loads a map.
	Map(const char* filename);
	~Map();

	// Creates and saves to a file
	static void CreateMap( 
			   char* filename, int key, 
			   const int roomHeight=8, const int roomWidth=8, 
			   const int horizontalNumRooms=32, const int verticalNumRooms=32, 
			   const int doorwayWidth=1 );
};

#endif
